import java.util.ArrayList;
import java.util.List;

public class TREE {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left,right;
        if(root.left==null){
            left=1;
        }else {
            left=1+maxDepth(root.left);
        }
        if(root.right==null){
            right=1;
        }else {
            right=1+maxDepth(root.right);
        }
        return left>right?left:right;
    }

    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }else {

        }
        if(isBig(root.left,root.val)){
           if(isValidBST(root.left));
           else return false;
        }else {
            return false;
        }
        if(isSmall(root.right,root.val)){
            if(isValidBST(root.right));
            else return false;
        }else return false;
        return true;
    }

    public boolean isBig(TreeNode root,int val){
        if(root==null)return true;
        else {
            if(root.val>=val)return false;
            else {
                if(isBig(root.left,val)&&isBig(root.right,val))return true;
                else return false;
            }
        }
    }
    public boolean isSmall(TreeNode root,int val){
        if(root==null)return true;
        else {
            if(root.val<=val)return false;
            else {
                if(isSmall(root.left,val)&&isSmall(root.right,val))return true;
                else return false;
            }
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return isSymmetric(root.left,root.right);
    }
    public boolean isSymmetric(TreeNode left,TreeNode right){
        if(left==null&&right==null)return true;
        else if(left==null||right==null)return false;
        if(left.val==right.val){
            if(isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left)) return true;
            else return false;
        }else {
            return false;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        int lenth=maxDepth(root);
        List<List<Integer>> result=new ArrayList<>();
        for (int i=0;i<lenth;i++){
            result.add(new ArrayList<>());
        }
        result=levelOrder(root,0,result);
        return result;
    }

    public List<List<Integer>> levelOrder(TreeNode root,int lenth,List<List<Integer>> result) {
        if(root!=null){
            result.get(lenth).add(root.val);
            lenth++;
            result=levelOrder(root.left,lenth,result);
            result=levelOrder(root.right,lenth,result);
        }
        return result;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0)return null;
        return sortedArrayToBST(nums,0,nums.length-1);
    }

    public TreeNode sortedArrayToBST(int[] nums,int start,int end) {
        int i=(start+end+1)/2;
        TreeNode root=new TreeNode(nums[i]);
        if(i!=start){
            root.left=sortedArrayToBST(nums,start,i-1);
        }
        if(i!=end){
            root.right=sortedArrayToBST(nums,i+1,end);
        }
        return root;
    }
}
